`
https://leetcode.cn/problems/shopping-offers/
`

/**
 * @param {number[]} price
 * @param {number[][]} special
 * @param {number[]} needs
 * @return {number}
 */
var shoppingOffers = function (price, special, needs) {
  // 记录当前购买大礼包的花费
  let trackCost = 0
  // 记录最少花费
  let minCost = Infinity

  // 先去除那些还不如单买的礼包
  const newSpecial = []
  for (const spe of special) {
    // 单买需要的价格
    let cost = 0
    for (let i = 0; i < spe.length - 1; i++) {
      cost += spe[i] * price[i]
    }
    if (cost > spe[spe.length - 1]) {
      newSpecial.push(spe)
    }
  }

  // 回溯思路：类似「元素无重可复选」的组合问题
  // 先不断选择不同类型不同数量的礼包，直到礼包选不了了再单买
  function backtrack(index) {

    // 是否需要购买当前的礼包
    let needUseSpecial = false

    for (let i = index; i < newSpecial.length; i++) {
      const targetSpecial = newSpecial[i]
      // 判断是否需要购买礼包
      if (!isNeedUseSpecial(targetSpecial, needs)) {
        continue
      }

      // 否则就是需要购买礼包
      needUseSpecial = true

      // 做出购买大礼包的选择
      for (let j = 0; j < needs.length; j++) {
        needs[j] -= targetSpecial[j]
      }
      trackCost += targetSpecial[targetSpecial.length - 1]

      // 因为可以重复购买礼包，所以从当前索引进入下一层
      backtrack(i)

      // 撤销购买大礼包的选择
      for (let j = 0; j < needs.length; j++) {
        needs[j] += targetSpecial[j]
      }
      trackCost -= targetSpecial[targetSpecial.length - 1]
    }

    if (!needUseSpecial) {
      // 无法使用大礼包，只能单买
      let sum = 0
      for (let i = 0; i < needs.length; i++) {
        sum += needs[i] * price[i]
      }
      // 单买的价格加上之前的大礼包的价格
      minCost = Math.min(minCost, sum + trackCost)
    }
  }

  backtrack(0)
  return minCost
};

function isNeedUseSpecial(special, needs) {
  // 如果有一个要购买物品的数量小于礼包里对应的物品数量，说明不需要购买礼包
  for (let i = 0; i < needs.length; i++) {
    if (needs[i] < special[i]) {
      return false
    }
  }
  return true
}